package com.wj.linear;

import java.util.Iterator;
import java.util.Objects;

/**
 * 双向链表
 *  @author wen.jie
 * @date 2021/8/6 14:10
 */
public class DoublyLinkedList<T> implements Iterable<T>{

    //头节点
    protected Node<T> head;

    //尾节点
    protected Node<T> last;

    //长度
    int size = 0;

    protected static class Node<T> {
        protected T item;
        protected Node<T> pre;
        protected Node<T> next;

        public Node (T item, Node<T> pre, Node<T> next){
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }

    public DoublyLinkedList() {
        this.head = new Node<>(null, null, null);
        this.last = null;
    }

    public void clear(){
        this.head.next = null;
        this.last = null;
        this.size = 0;
    }

    public int size(){
        return size;
    }

    public T getFirst(){
        if(isEmpty()){
            return null;
        }
        return this.head.next.item;
    }

    public T getLast(){
        if(isEmpty()){
            return null;
        }
        return this.last.item;
    }

    protected void putLast(T t){
        Node<T> node = new Node<>(t, last, null);
        this.last.next = node;
        this.last = node;

    }

    /**
     * 把节点t插入到pre和last之间
     * @author wen.jie
     * @date 2021/8/9 22:30
     */
    protected void insert(T t, Node<T> pre, Node<T> last) {
        Node<T> tNode = new Node<>(t, pre, last);
        pre.next = tNode;
        last.pre = tNode;
    }

    public void add(T t){
        if (isEmpty()){
            Node<T> node = new Node<>(t, head, null);
            head.next = node;
            last = node;
        }else {
            putLast(t);
        }
        size++;
    }

    /**
     * 指定位置处插入元素
     * @author wen.jie
     * @date 2021/8/6 14:41
     */
    public void add(int i, T t) {
        Node<T> pre = head;
        for(int index = 0; index< i; index++){
            pre = pre.next;
        }
        insert(t, pre, pre.next);
        size++;
    }

    /**
     * 获取指定位置i处的元素
     * @author wen.jie
     * @date 2021/8/6 14:48
     */
    public T get(int i) {
        Node<T> n = head.next;
        for(int index = 0; index< i; index++){
            n = n.next;
        }
        return n.item;
    }

    /**
     * 元素T在链表第一次出现的位置
     * @author wen.jie
     * @date 2021/8/6 14:48
     */
    public int indexOf(T t) {
        Node<T> n = head.next;
        for(int i = 0; n.next!=null; i++){
            n = n.next;
            if(Objects.equals(t, n))
                return i;
        }
        return -1;
    }

    /**
     * 删除指定i位置处的元素
     * @author wen.jie
     * @date 2021/8/6 14:50
     */
    public T remove(int i){
        Node<T> pre = head;
        for(int index = 0; index < i; index++){
            pre = pre.next;
        }
        Node<T> curr = pre.next;
        Node<T> tNode = curr.next;
        pre.next = tNode;
        tNode.pre = pre;
        size--;
        return curr.item;
    }

    public boolean isEmpty(){
        return size == 0;
    }


    @Override
    public Iterator<T> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<T> {

        private Node<T> n;

        public Itr(){
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public T next() {
            n = n.next;
            return n.item;
        }
    }
}
